package Sort;

/**
 * @Author Fizz Pu
 * @Date 2021/7/30 上午8:35
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// 堆排序
// 最大堆

public class Heap {
    private int[] arr;
    private int count; // 有效元素个数
    public Heap(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException();
        }
        this.arr = arr;
        count = arr.length;
    }

    // 从最后一个元素的节点的父亲节点上滑开始调整
    void build1() {
        //todo
        // 通过插入实现
    }

    void build2() {
        for (int i = 0; i <= count; i++) {
            siftUp(0, i);
        }
    }

    void build3() {
        for (int i = count - 1; i >= 0; i--) {
            siftDown(i, count - 1);
        }
    }

    int getTop() {
        return arr[0];
    }

    int remove() {
        if (count <= 0) {
            throw new RuntimeException();
        }

        int swap = arr[0];
        arr[0] = arr[count-1];
        arr[count-1] = swap;
        count--;
        siftDown(0, count - 1);

        return swap;
    }

    private void siftDown(int start, int end) {

            int parent = start;
            int leftChild;
            int rightChild;
            int tmp;

        while ((leftChild = parent * 2 + 1) <= end) {
            tmp = leftChild;
            if (leftChild < end) {
                rightChild = leftChild + 1;

                if (arr[rightChild] > arr[leftChild]) {
                    tmp = rightChild;
                }
            }

            if (arr[tmp] <= arr[parent]) {
                break;
            }

            int swap = arr[parent];
            arr[parent] = arr[tmp];
            arr[tmp] = swap;
            parent = tmp;
        }
    }

    private void siftUp(int start, int end) {
        int child = end;
        int parent = 0;

        while ((parent = (child - 1) / 2) >= start && arr[parent] < arr[child]) {
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                child = parent;
            }
        }
    }

